/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/text-justification
   @Language: C++
   @Datetime: 19-07-02 14:00
   */

class Solution {
public:
	vector<string> fullJustify(vector<string>& words, int maxWidth) {
		vector<string> res;
		int n=words.size();
		for(int i=0, j=0, l=0; i<n;){
			for(j=i, l=0; j<n && l+words[j].length()+j-i<=maxWidth; l+=words[j++].length());
			string line;
			if(j==n){
				for(; i<j; line.append(words[i++]+' '));
				for(; line.length()<maxWidth; line.push_back(' '));
				if(line.length()>maxWidth) line.pop_back();
			}
			else{
				int s=maxWidth-l, c=j-i-1;
				for(int k=0; i<j; ++i, s-=k, --c){
					line.append(words[i]);
					if(!c) continue;
					for(k=0, l=s/c+(s%c?1:0); k<l; ++k, line.push_back(' '));
				}
				for(; line.length()<maxWidth; line.push_back(' '));
			}
			res.push_back(line);
		}
		return res;
	}
};
